As ATM cells traverse an ATM switch from an input port to an output port, they are stored temporarily in buffers at various stages of the switch. There are several types of buffers. One type of buffer is a shared memory buffer. In a shared memory buffer, cells are assigned to queues which correspond to output ports of the stage of the switch, and these queues share the same physical memory. One of the challenges in designing a shared memory buffer is buffer and queue management.
Buffer management consists of allocating space in the shared memory for the queues as they grow and reclaiming space in the memory as the queues shrink. Queue management consists of tracking the cells that are in the queue by tracking the addresses of those cells within the shared memory in lists. As cells are added to the queue, addresses are added to the list and as cells are read from the queue, they are removed. Buffer and queue management are closely related.
Current shared memory buffer and queue management techniques vary in the way they maintain queues in physical memory and in the way they handle unicast and multicast cells. These two types of cells differ in that a unicast cell is destined for only one output port of the buffer and a multicast cell can be destined for several output ports. One management strategy consists of dividing the shared memory into small blocks and organizing the queues as FIFOs (first-in first-out) containing linked lists of memory blocks. Each cell is stored in only one queue and the queues are tracked by means of block pointers. Typically, there is one unicast queue for each output port and one multicast queue which serves all of the output ports. This scheme is memory efficient but presents problems for multicast. Since a multicast cell is stored in a single multicast queue, a sophisticated scheduling algorithm is needed in order to choose between the multicast queue and several unicast queues as cells are read from the buffer and sent to the output ports of the switch stage since the cells in the multicast queue go to several output ports. Another problem with this strategy is head-of-the-line blocking within the multicast queue.
A second management strategy consists of organizing the queues as FIFOs (first-in first-out) that hold shared memory addresses of cells. It should be noted that adjacent cells in the FIFO can be stored in memory addresses that are not necessarily adjacent. One FIFO exists for each output port, and both unicast and multicast cells are stored in it. A copy of the multicast cell is placed in the FIFO of each destination in the multicast. This scheme has the advantage of requiring a simpler scheduling algorithm and not suffering from head-of-the-line blocking but requires very large memories for the address FIFOs.
The present invention describes a hybrid buffer and queue management scheme in which queues consisting of unicast ATM cells are organized as linked-lists of memory blocks and queues consisting of multicast ATM cells are organized as address lists. This scheme has the advantage of being very memory efficient for unicast queue management, uses a shared memory for both unicast and multicast cells, and requires a simple scheduling algorithm for reading cells from the buffer.